\section{Performance Analysis} %chen+tom
   
    Because most optimisation in Java is done at runtime using Just-In-Time (JIT) compilation, there is not much to choose from in the way
  	 of compiler flags. The way in which a problem is laid out is always very important, however, so our main aim in performance testing
 	 was to identify inefficiencies within the code itself, such as unnecessary loops and calls to methods.\newline{}
 	
 	 Profiling of the code was done mostly with NetBeans and the unix \emph{time} command. Parameters were varied to asses the effect of a number of 
 	 factors, most notably overhead, output write time, and the effect of map size and complexity.\newline{}
 
 	 One of the main things which we identified	very quickly as a bottleneck was the output . Fortunately, implementing a bufered writer is
	 very easy in Java; this alone increased performance by a factor of 5-6 (see Figure \ref{buffering}).\newline{}
	 
	The performance of the program could be increased even further by having the output in a more efficient format. This can be shown more 
   simply by running the code with an output frequency of 50 timesteps compared with an output frequency of 5000 timesteps (a single output for a t=0..500, timestep=0.4
   simulation). This give run times of $\sim$21.5 and $\sim$17.0 seconds respectively, even with buffered output. This output then accounts for 
   $\sim$ 17\% of the computation time of a simulation, which is obviously not ideal.  \newline{}

	
  \begin{figure}[H]
  \begin{center}
  \input{figs/buffering}
  \caption{\label{buffering}This graph shows the advantage of using a buffered file writer over repeated calls to the printf() method. 
  The data was generated from a simulation using a 100x100 grid, but results will be similar for all grid sizes, since write time and computation
  time (neglecting overhead) both scale linearly with the number of cells.}
  \end{center}
  \end{figure} 

	 In Figure \ref{overhead} we attempt to quantify the overhead in our code. This is done by calculating the total time spent on each cell in a 
	 simulation, relative to the size of the simulation. With this metric, the code actually becomes `slower' for smaller simulations. This is 
	 because a significant fraction of the simulation time is being spent on finding arrays of neighbours and other `non essential' tasks. The graph
	 shows that our code only begins to run as efficiently as possible once grids of $\sim$100x100 are used, above which the simulation time scales
	 almost exactly as the number of cells (the flat part of Figure \ref{overhead}).\newline{}

	 
	 Using this, we can find how long our program takes to update a single cell, giving us a useful way of quantifying the speed. The value on the 
	 graph is roughly $10^{-3.27}$s per cell over the whole simulation. Thus, $10^{-3.27}/1200$, where 1200 is the number of timesteps, gives us the 
	 time per cell per timestep: $\sim$450 nanoseconds. This allows us to predict how long a given simulation should take (on the machine use to
	 generate this data, at least). For instance, if we had a $10000\times10000$ array, this would should take $10000^{2}\times N$, where $N$ is the 
	 number of timesteps. For the same number of steps this is about 15 hours!
	 
	 \newpage{}
	 
  \begin{figure}[H]
  \begin{center}
  \input{figs/overhead}
  \caption{\label{overhead}This is a graph of total time spent on each cell, which shows that overheads such as array initialization
  take up a significant fraction of computation time with grids smaller than $\sim$100 by 100.}
  \end{center}
  \end{figure}
  
  
  \begin{figure}[H]
  \begin{center}
  \subfloat[]{\includegraphics[width=40mm]{figs/emptypic.png}}
  \subfloat[]{\input{figs/empty}}
  \caption{\label{empty}This shows the effect of fill percentage on run time. The six panels in a) are the input maps used, all of which were
  300x300. As expected, the computation time increases fairly linearly with
  the amount of land, since the bulk of the main algorithm is only run for land cells.}
  \end{center}
  \end{figure}
  
  \newpage{}
  
  
  The effect of map complexity is also discussed in Figure \ref{empty}. As expected, we found that the code was totally insensitive to
  complexity, being affected mostly by the total number of land cells. This is because most of the density update algorithm is never implemented for water 
  cells, and checking whether a cell is land or water does not take much time compared to a full density update.
  
  
